/**
 * @file PostThreadBinaryTree.c
 * @desc 带详细注解的后序线索二叉树示例（Post-order threaded binary tree）
 *       注释风格与原始文件保持一致：中文说明 + doxygen 风格的函数注释
 * @author WangBlue (wangjiping596@gmail.com)
 * @date 2025/10/16 09:59
 * @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * @struct BinNode
 * @brief 线索二叉树节点结构
 *
 * 字段说明：
 *  - data: 节点保存的字符数据
 *  - lChild, rChild: 左、右孩子指针；在线索存在时，指向前驱/后继
 *  - parent: 父节点指针（用于在后序线索化后方便查找前驱/后继）
 *  - ltag, rtag: 标志位，0 表示指针指向孩子，1 表示该指针是线索（指向前驱/后继）
 */
typedef struct BinNode {
    char data;
    struct BinNode *lChild, *rChild, *parent;
    int rtag, ltag; // 0: 子指针，1: 线索
} BinNode;

/**
 * @brief 创建并初始化一个二叉树节点
 *
 * @param data 节点保存的字符
 * @return BinNode* 分配成功返回指针，失败返回 NULL
 */
BinNode *createTreeNode(char data) {
    BinNode *node = (BinNode *) malloc(sizeof(BinNode));
    if (!node) return NULL;
    node->data = data;
    node->lChild = NULL;   // 初始无孩子
    node->rChild = NULL;
    node->parent = NULL;   // 初始无父节点，构建树后由调用者设置
    node->rtag = node->ltag = 0; // 默认指针都是孩子指针
    return node;
}


/**
 * @brief 构建一棵简单的示例二叉树，用于测试
 *
 * 树结构如下：
 *        A
 *       / \
 *      B   C
 *     / \
 *    D   E
 *
 * @return BinNode* 返回根节点指针
 */
BinNode *createSimpleTree() {
    BinNode *A = createTreeNode('A');
    BinNode *B = createTreeNode('B');
    BinNode *C = createTreeNode('C');
    BinNode *D = createTreeNode('D');
    BinNode *E = createTreeNode('E');

    // 建立孩子关系（注意：此时还未处理父指针）
    A->lChild = B;
    A->rChild = C;
    B->lChild = D;
    B->rChild = E;

    // 建立父指针，便于后序线索化后查找前驱/后继
    B->parent = A;
    C->parent = A;
    D->parent = B;
    E->parent = B;
    return A;
}

/**
 * @brief 递归后序遍历并打印节点数据（用于验证树结构）
 *
 * @param root 根节点
 */
void postOrder(BinNode *root) {
    if (!root) return;
    postOrder(root->lChild);
    postOrder(root->rChild);
    printf("%c ", root->data);
}

/**
 * @brief 对单个节点进行后序线索化时的访问操作（设置前驱/后继线索）
 *
 * 说明：在后序线索化中，我们按后序访问节点。使用外部维护的指针 `pre`
 * 指向上一次访问的节点（即当前节点的前驱）。visit 的任务是：
 *  - 如果当前节点左孩子为空，则把 left 指针设为指向前驱，并标记 ltag=1（左线索）
 *  - 如果前驱的右孩子为空，则把前驱的 right 指针设为指向当前节点，并标记 rtag=1（右线索）
 *
 * @param root 当前访问节点
 * @param pre 指向保存前驱节点指针的外部变量的指针（调用者维护）
 */
void visit(BinNode *root, BinNode **pre) {
    if (!root) return;

    // 如果左孩子为空，用左指针建立前驱线索
    if (!root->lChild) {
        root->ltag = 1;      // 标记为线索
        root->lChild = *pre; // 指向前驱（可能为 NULL，如第一个访问节点）
    }

    // 如果前驱存在且前驱的右孩子为空，则把前驱的右指针设为当前节点（建立后继线索）
    if ((*pre) && !(*pre)->rChild) {
        (*pre)->rtag = 1;
        (*pre)->rChild = root;
    }

    // 更新 pre 为当前节点，供下一个访问节点使用
    *pre = root;
}

/**
 * @brief 对整棵树进行后序线索化（递归实现）
 *
 * 规则：在递归遍历时，遇到非线索的左/右子树先递归处理，然后对当前节点调用 visit
 *  - 使用 ltag/rtag 判断指针是否已经被线索化，避免重复递归或错误进入线索指针
 *
 * @param root 当前子树根
 * @param pre 指向用于保存前驱节点指针的变量（外部维护）
 */
void postThreadBinaryTree(BinNode *root, BinNode **pre) {
    if (!root) return;
    // 仅当 left 指针是真正的孩子（ltag==0）时，才递归左子树
    if (root->ltag == 0) postThreadBinaryTree(root->lChild, pre);
    // 仅当 right 指针是真正的孩子（rtag==0）时，才递归右子树
    if (root->rtag == 0) postThreadBinaryTree(root->rChild, pre);
    // 处理当前节点：建立前驱/后继线索
    visit(root, pre);
}

/**
 * @brief 找到给定子树中按照后序顺序的第一个节点（最靠前被访问的节点）
 *
 * 对于后序（L,R,Root），第一个被访问的节点通常是沿左子树一路走到底，
 * 如果无法继续左移则尝试右移，直到到达叶子节点或线索指针阻止进一步移动。
 *
 * 此函数用于在从某一子树开始顺序遍历时定位起始节点。
 *
 * @param node 子树根
 * @return BinNode* 返回后序中的第一个节点指针
 */
BinNode *firstNode(BinNode *node) {
    if (!node) return NULL;
    // 优先沿着真实左子树下探（ltag==0 表示存在孩子指针）
    while (node->ltag == 0 && node->lChild) {
        node = node->lChild;
    }
    // 然后尝试沿真实右子树下探，直到不能再下探
    while (node->rtag == 0 && node->rChild) {
        node = node->rChild;
    }
    return node;
}

/**
 * @brief 在后序线索化的树上查找节点的前驱（前一个被访问的节点）
 *
 * 算法要点（后序遍历的前驱关系较中序/前序复杂）：
 * 1. 如果存在左线索（ltag==1），左指针直接指向前驱，返回即可。
 * 2. 否则，通过父指针推断：
 *    - 若节点为父节点的右孩子：则前驱是父节点的左子树的后序“最后一个”节点（如果左子树存在），
 *      否则前驱就是父节点本身（左子树为空的情况）。
 *    - 若节点为父节点的左孩子：则前驱就是父节点（因为在后序中父节点在右子树之后，左子树的最后节点之前）。
 * 3. 特殊情况：根节点或无父节点则没有前驱，返回 NULL。
 *
 * @param node 要查找前驱的节点
 * @return BinNode* 前驱节点指针或 NULL（无前驱）
 */
BinNode* preNode(BinNode* node) {
    if (!node) return NULL;

    // 如果 left 是线索，则直接返回左线索所指的前驱
    if (node->ltag == 1) return node->lChild;

    BinNode* parent = node->parent;
    // 若无父节点（例如只有一个节点的树），则没有前驱
    if (!parent) return NULL;

    // 当前节点是父节点的右子树
    if (parent->rChild == node) {
        if (parent->lChild) {
            // 前驱是左子树的最后一个后序节点
            BinNode* temp = parent->lChild;
            while (1) {
                if (temp->ltag == 0 && temp->lChild) {
                    temp = temp->lChild; // 优先下探左子树
                } else if (temp->rtag == 0 && temp->rChild) {
                    temp = temp->rChild; // 若左不可下探再下探右子树
                } else {
                    break; // 到达叶子或线索阻止继续下探
                }
            }
            return temp;
        } else {
            // 父节点左子树为空，按后序规则，左子树没有节点，父节点即为前驱
            return parent;
        }
    }

    // 当前节点是父节点的左子树（parent->lChild == node）
    // 对于左子树的节点，其前驱就是父节点（后序中父节点会在右子树之后访问，但左子树的最后节点之前）
    if (parent->lChild == node) {
        return parent;
    }

    return NULL; // 兜底（一般不会到达此处）
}

/**
 * @brief 在后序线索化的树上查找节点的后继（下一个被访问的节点）
 *
 * 规则：
 * 1. 若存在右线索（rtag==1），则右指针直接指向后继，返回该指针
 * 2. 否则，使用父指针判断：
 *    - 如果当前节点是父节点的右子树，或者父节点没有右子树（即当前节点实际上是父的最后访问者），
 *      则后继是父节点。
 *    - 否则（当前节点是父节点的左孩子且父有右子树），则后继是父节点右子树的后序第一个节点（firstNode）
 *
 * @param root 当前节点
 * @return BinNode* 后继节点或 NULL（无后继）
 */
BinNode *nextNode(BinNode *root) {
    if (!root) return NULL;

    // 如果 rtag==1，右指针是线索，直接返回指向的后继
    if (root->rtag == 1) {
        return root->rChild;
    }

    BinNode *parent = root->parent;

    // 如果没有父节点（例如只有一个节点），则没有后继
    if (!parent) return NULL;

    // 如果当前节点是父节点的右孩子，或父节点没有右孩子（说明当前节点是父的最后访问者），后继为父节点
    if (parent->rChild == root || !parent->rChild) {
        return parent;
    } else {
        // 否则后继为父节点右子树的第一个后序节点
        return firstNode(root->rChild);
    }
}

/**
 * @brief 在整个（线索化后的）树上从后序第一个节点开始按后继遍历查找特定数据的节点
 *
 * 说明：利用 firstNode 和 nextNode 在后序线索化的树上顺序迭代。
 *
 * @param node 树的根（或子树根）
 * @param target 目标字符
 * @return BinNode* 找到则返回对应节点，否则返回 NULL
 */
BinNode* findNode(BinNode* node, char target) {
    if (node == NULL) return NULL;

    // 从子树的第一个后序节点开始遍历，直至 nextNode 返回 NULL
    for (BinNode* p = firstNode(node); p != NULL; p = nextNode(p)) {
        if (p->data == target)
            return p;
    }
    return NULL;
}

/**
 * @brief 主函数：构建示例树、打印后序、线索化并演示查找前驱/后继
 */
int main() {
    // 1. 创建测试树
    BinNode *root = createSimpleTree();

    // 2. 打印后序遍历（用于验证树结构是否正确）
    postOrder(root);

    // 3. 对树进行后序线索化（使用 pre 指针保存上一个访问节点）
    BinNode *pre = NULL;
    postThreadBinaryTree(root, &pre);

    printf("\n");

    // 4. 查找节点 E 并打印其前驱与后继
    BinNode* E = findNode(root, 'E');
    BinNode* prNode = preNode(E);
    if (prNode) {
        printf("The predecessor of node E is: %c\n", prNode->data);
    } else {
        printf("Node E has no predecessor.\n");
    }
    BinNode* postNode = nextNode(E);
    if (postNode) {
        printf("The successor of node E is: %c\n", postNode->data);
    } else {
        printf("Node E has no successor.\n");
    }

    return 0;
}
